{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Word2Vec \n",
    "\n",
    "## 主要思想：\n",
    "\n",
    "**一个词的含义应该是由该词的上下文来决定的。**\n",
    "\n",
    "1、我们有一个很大的语料库，这个语料库包含了很多的 text\n",
    "\n",
    "2、所有的单词都可以用一个向量表示\n",
    "\n",
    "3、我们使用一个中心词 $c$ 和上下文 $o$ 来遍历 text 中的每个位置 $t$\n",
    "\n",
    "4、使用 $c$ 和 $o$ 的词向量的相似度来计算 $P(o|c)$\n",
    "\n",
    "5、最大化这个概率。\n",
    "\n",
    "6、上述步骤结束之后，我们得到的权重矩阵，就可以看作是单词的 vector\n",
    "\n",
    "\n",
    "### 两个模型：\n",
    "\n",
    "* skip-grams: 给定单词来预测上下文\n",
    "\n",
    "* CBOW: 给定上下文来预测单词\n",
    "\n",
    "### 两个高效的训练方法：\n",
    "\n",
    "* Hierarchical Softmax (这东西我看的也不是很懂，秉着不求甚解的精神，我决定不看这个了)\n",
    "\n",
    "* Negative sampling\n",
    "\n",
    "\n",
    "这里的模型 + 训练方法一共可以有四种组合。\n",
    "\n",
    "这里，只会写 skip-grams 模型以及 skip-grams + Negative sampling，其余内容如果有兴趣，可以自行编写，或者以后我想写了再补齐（就是这么任性~）\n",
    "\n",
    "这里只简单地讲述主要思想和实现方式，更多的内容，可以观看 [CS224N 第二课](https://www.bilibili.com/video/av13383754/?from=search&seid=17986192997424429774#page=2) 和 [CS224N 第三课](https://www.bilibili.com/video/av13383754/?from=search&seid=17986192997424429774#page=3)\n",
    "\n",
    "结合第二课、第三课还有吴恩达的DeepLearning 系列课程，这里还有个补充，在自己的个人博客里面 [Word2vec](https://lianhaimiao.github.io/2018/03/14/word2vec/#more)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## skip-grams模型\n",
    "\n",
    "\n",
    "奉献一张，我心中认为的解读 skip-grams模型 最棒的图，一图胜千言。\n",
    "\n",
    "![skip-grams](./word2vec/skipgram.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch.autograd import Variable\n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# 构建 skip-grams 模型\n",
    "\n",
    "class SkipGramModel(nn.Module):\n",
    "    def __init__(self, vocab_size, emb_dim):\n",
    "        \"\"\"\n",
    "            vocab_size: 语料库中的单词的数量\n",
    "            emb_dim: 向量的维度\n",
    "        \"\"\"\n",
    "        super(SkipGramModel, self).__init__()\n",
    "        self.vocab_size = vocab_size\n",
    "        self.emb_dim = emb_dim\n",
    "        self.embedding_v = nn.Embedding(vocab_size, emb_dim) # center word embedding\n",
    "        self.embedding_u = nn.Embedding(vocab_size, emb_dim) # out word embedding\n",
    "        self.init_emb()\n",
    "    \n",
    "    def forward(center_words, target_words, outer_words):\n",
    "        center_embeds = self.embedding_v(center_words) # B x 1 x D\n",
    "        target_embeds = self.embedding_u(target_words) # B x 1 x D\n",
    "        outer_embeds = self.embedding_u(outer_words) # B x V x D\n",
    "        \n",
    "        scores = target_embeds.bmm(center_embeds.transpose(1, 2)).squeeze(2) # Bx1xD * BxDx1 => Bx1 \n",
    "        norm_scores = outer_embeds.bmm(center_embeds.transpose(1, 2)).squeeze(2) # BxVxD * BxDx1 => BxV\n",
    "        \n",
    "        P_oc = torch.exp(scores) / torch.sum(torch.exp(norm_scores), 1).unsqueeze(1) # Bx1 * Bx1 => B*1 表示 B个单词的 P(o|c)\n",
    "        nll = -torch.mean(torch.log(P_oc)) # 求 这 B 个单词的 negative log likelihood\n",
    "\n",
    "        return nll \n",
    "    \n",
    "    def init_emb(self):\n",
    "        \"\"\"\n",
    "            初始化网络权重\n",
    "        \"\"\"\n",
    "        initrange = 0.5 / self.emb_dimension\n",
    "        self.u_embeddings.weight.data.uniform_(-initrange, initrange)\n",
    "        self.v_embeddings.weight.data.uniform_(-0, 0)\n",
    "        return \n",
    "    \n",
    "    def prediction(self, inputs):\n",
    "        \"\"\"\n",
    "            给出 word 的 vector, 这里，我们没有用到后面的 embedding_u，其实这里还有几种做法：\n",
    "            1、embedding_v + embedding_u； \n",
    "            2、embedding_v[:, N/2; :] + embedding_u[:; :, N/2] 也就是 embedding_v 取前一半， embedding_u取后一半，两者拼接。\n",
    "        \"\"\"\n",
    "        embeds = self.embedding_v(inputs)\n",
    "        return embeds \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## skip-grams模型 +  Negative sampling\n",
    "\n",
    "**为什么需要使用 Negative sampling ？？**\n",
    "\n",
    "因为词表V的量级非常大，会导致公式 $P(o|c) = \\frac{exp (u_o^T v_c) }{\\sum_{w=1}^V exp (u_w^T v_c) }$ 的分母计算量大。\n",
    "\n",
    "所以，为了简化运算我们采用 Negative sampling\n",
    "\n",
    "**什么是 Negative sampling ？？**\n",
    "\n",
    "其实，所谓的 Negative sampling 就是每次训练的时候，对于一对训练样本(一个中间词 $c$ 和一个上下文单词 $o$)，我们从语料库中随机的选取 $k$ 个单词作为负样本一同进行训练，当然，这时候的目标函数也会变化。\n",
    "\n",
    "**如何使用Negative sampling ？？**\n",
    "\n",
    "我们的目标函数优化变成 $J_t(\\theta) = log \\sigma(u_o^T v_c) + \\sum_{i=1}^k E_{j \\thicksim P(w)} [log \\sigma(-u_j^T v_c)]$\n",
    "\n",
    "解释一下：$\\sigma$ 是 sigmoid 函数， $t$ 是某个窗口， $k$ 是采样个数。 $P(w)$ 是 unigram 分布\n",
    "\n",
    "再对 $P(w)$ 进行一下解释：\n",
    "\n",
    "由于任何采样算法都应该保证频次越高的样本越容易被采样出来。基本的思路是对于长度为1的线段，根据词语的词频将其公平地分配给每个词语：\n",
    "\n",
    "$$len(w) = \\frac{counter(w)}{\\sum_{u \\in D} counter(u)}$$\n",
    "\n",
    "counter就是w的词频。\n",
    "\n",
    "于是我们将该线段公平地分配了：\n",
    "\n",
    "   ![neg_sample](./word2vec/neg_sample.jpg)\n",
    "\n",
    "接下来我们只要生成一个0-1之间的随机数，看看落到哪个区间，就能采样到该区间对应的单词了，很公平。\n",
    "\n",
    "但怎么根据小数找区间呢？速度慢可不行。\n",
    "\n",
    "word2vec用的是一种查表的方式，将上述线段标上M个“刻度”，刻度之间的间隔是相等的，即1/M：\n",
    "\n",
    "\n",
    "   ![neg_sample](./word2vec/kedu.jpg)\n",
    "\n",
    "\n",
    "接着我们就不生成0-1之间的随机数了，我们生成0-M之间的整数，去这个刻度尺上一查就能抽中一个单词了。\n",
    "\n",
    "在word2vec中，该“刻度尺”对应着table数组。具体实现时，对词频取了0.75次幂：\n",
    "\n",
    "\n",
    "$$len(w) = \\frac{[ {counter(w) ]}^{0.75} }{\\sum_{u \\in D} {[counter(u)]}^ {0.75} }$$\n",
    "\n",
    "\n",
    "这个幂实际上是一种“平滑”策略，能够让低频词多一些出场机会，高频词贡献一些出场机会，劫富济贫。\n",
    "\n",
    "\n",
    "**负采样算法的解释参考 [word2vec原理推导_负采样算法](http://www.hankcs.com/nlp/word2vec.html#h3-12)**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class SkipgramNegSampling(nn.Module):\n",
    "    def __init__(self, vocab_size, emb_dim):\n",
    "        super(SkipgramNegSampling, self).__init__()\n",
    "        self.vocab_size = vocab_size\n",
    "        self.emb_dim = emb_dim\n",
    "        self.embedding_v = nn.Embedding(vocab_size, emb_dim) # center word embedding\n",
    "        self.embedding_u = nn.Embedding(vocab_size, emb_dim) # out word embedding\n",
    "        self.logsigmoid = nn.LogSigmoid()\n",
    "        self.init_emb()\n",
    "        \n",
    "    def forward(self, center_words, target_words, negative_words):\n",
    "        center_embeds = self.embedding_v(center_words) # B x 1 x D\n",
    "        target_embeds = self.embedding_u(target_words) # B x 1 x D\n",
    "        neg_embeds = -self.embedding_u(negative_words) # K个负样本 B x K x D  \n",
    "        \n",
    "        positive_score = target_embeds.bmm(center_embeds.transpose(1, 2)).squeeze(2) # Bx1xD * BxDx1 -> Bx1\n",
    "        \n",
    "        negative_score = neg_embeds.bmm(center_embeds.transpose(1, 2)).squeeze(2) # BxKxD * BxDx1 -> BxK\n",
    "        \n",
    "        negative_score = torch.sum(negative_score, 1).view(negs.size(0), -1) # BxK -> Bx1\n",
    "        \n",
    "        loss = self.logsigmoid(positive_score) + self.logsigmoid(negative_score)\n",
    "        \n",
    "        return -torch.mean(loss) # 原目标函数是最大化的，加一个负号，变成 min 然后就可以使用SGD等优化算法了。\n",
    "    \n",
    "    \n",
    "    def prediction(self, inputs):\n",
    "        embeds = self.embedding_v(inputs)\n",
    "        return embeds\n",
    "\n",
    "    \n",
    "    def init_emb(self):\n",
    "        initrange = (2.0 / (self.vocab_size + self.emb_dim))**0.5 # Xavier init\n",
    "        self.embedding_v.weight.data.uniform_(-initrange, initrange) # init\n",
    "        self.embedding_u.weight.data.uniform_(-0.0, 0.0) # init\n",
    "        return "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Todo: 找一个小词库，自己过一遍训练词向量的流程。"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
